﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0051_LetterCasePermutation : IAlgorithm
    {
        // 784. 字母大小写全排列

        // 给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。

        public void Test()
        {
            // 算法参数定义
            string s = "a1b2";
            // 算法执行与打印
            foreach (var item in LetterCasePermutation(s))
            {
                Console.WriteLine(item);
            }
        }

        // 算法
        public IList<string> LetterCasePermutation(string s)
        {
            if (string.IsNullOrEmpty(s))
                return new List<string>();
            s = s.ToLower();
            var res = new List<string>();
            var chars = new List<char>();
            LetterCasePermutation(s, 0, chars, res);
            return res;
        }
        private void LetterCasePermutation(string str, int s, List<char> chars, List<string> res)
        {
            if (chars.Count == str.Length)
                res.Add(new string(chars.ToArray()));
            else
                for (int i = s; i < str.Length; i++)
                {
                    if (str[i] - 'a' >= 0 && str[i] - 'a' <= 26)
                        for (int j = 0; j < 2; j++)
                        {
                            chars.Add(j == 0 ? str[i] : char.ToUpper(str[i]));
                            LetterCasePermutation(str, i + 1, chars, res);
                            chars.RemoveAt(chars.Count - 1);
                        }
                    else
                    {
                        chars.Add(str[i]);
                        LetterCasePermutation(str, i + 1, chars, res);
                        chars.RemoveAt(chars.Count - 1);
                    }
                }
        }

        public List<string> LetterCasePermutation1(string S)
        {
            var res = new List<string>();
            char[] chs = S.ToCharArray();
            int n = chs.Length;
            DFS(chs, n, 0, res);
            return res;
        }

        private void DFS(char[] chs, int n, int begin, List<string> res)
        {
            res.Add(new string(chs));
            for (int i = begin; i < n; i++)
            {
                if (!char.IsDigit(chs[i]))
                {
                    char tmp = chs[i];
                    chs[i] = (char)(chs[i] - 'a' >= 0 ? chs[i] - 32 : chs[i] + 32);
                    DFS(chs, n, i + 1, res);
                    chs[i] = tmp;
                }
            }
        }
    }
}
